//一棵二叉树顺序存储，将其变为二叉链表
#include <stdio.h>
#include <stdlib.h>

// 二叉树节点结构体，用于构建二叉链表
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 根据顺序存储的二叉树数组创建二叉链表
TreeNode* createBinaryTreeFromArray(int arr[], int index, int size) {
    if (index >= size || arr[index] == -1) {
        return NULL;
    }

    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->val = arr[index];

    // 递归构建左子树
    root->left = createBinaryTreeFromArray(arr, 2 * index + 1, size);

    // 递归构建右子树
    root->right = createBinaryTreeFromArray(arr, 2 * index + 2, size);

    return root;
}

// 释放二叉链表的内存空间
void freeBinaryTree(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    freeBinaryTree(root->left);
    freeBinaryTree(root->right);
    free(root);
}

// 中序遍历二叉链表并输出节点值，用于验证转换结果
void inorderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}

int main() {
    // 示例顺序存储的二叉树数组，-1表示空节点，可根据实际情况修改
    int arr[] = {1, 2, 3, 4, -1, 5, 6};
    int size = sizeof(arr) / sizeof(arr[0]);

    TreeNode *root = createBinaryTreeFromArray(arr, 0, size);

    printf("中序遍历转换后的二叉链表节点值：");
    inorderTraversal(root);
    printf("\n");

    freeBinaryTree(root);

    return 0;
}